package org.xingole.leetcode.dp;

import java.util.Arrays;

/**
 * <a href="https://leetcode.com/problems/stickers-to-spell-word/description/">
 * Problem Description
 * </a>
 * 
 * We are given n different types of stickers. Each sticker has lowercase English word on it.
 * 
 * You would like to spell out the given string target by cutting individual letters from your
 * collection of stickers and rearranging them. You can use each sticker more than once if you
 * want, and you have infinite quantities of each sticker.
 * 
 */
public class StickersToSpellWord {

    int best;
    int[][] stickersCount;
    int[] targetCount;

    /**
     * Return the minimum number of stickers that you need to spell out target.
     * If the task is impossible, return -1.
     */
    public int minStickers0(String[] stickers, String target) {
        /*
         * Approach 1: Optimized Exhaustive Search
         * 
         * A natural answer is to exhaustively search for combinations of stickers.
         * Because the data is randomized, there are many heuristics avaliable to us
         * that will make this fasters.
         * 
         *   - For all stickers, we can ignore any letters that are not in the target
         * word.
         *   - When our candidate's answer won't be smaller than an answer we have
         * already found, we can stop searching this path.
         *   - We should try to have our exhaustive search bound to the answer as soon
         * as possible, so the effect described in the above point happens more often.
         *   - When a sticker dominates another, we shouldn't include the dominant sticker
         * in our sticker collection.[Here, we say a sticker A dominates B if A.count(letter)
         * >= B.count(letter) for all letters.]
         */
        int[] targetNaiveCont = new int[26];
        for (char c : target.toCharArray()) {
            targetNaiveCont[c - 'a']++;
        }

        int[] index = new int[26];
        int t = 0;
        for (int i = 0; i < 26; i++) {
            if (targetNaiveCont[i] > 0) {
                index[i] = t++;
            } else {
                index[i] = -1;
            }
        }

        // Firstly, for each sticker, let's create a count of that sticker ( a mapping letter ->
        // sticker.count(letter) ) that does not consider letters not in the target word. Let A
        // be an array of these counts. Also, let's create t_count, a count of our target word.
        stickersCount = new int[stickers.length][t];
        for (int i = 0; i < stickers.length; i++) {
            for (char c : stickers[i].toCharArray()) {
                int j = index[c - 'a'];
                if (j >= 0) stickersCount[i][j]++;
            }
        }

        targetCount = new int[t];
        t = 0;
        for (int c : targetNaiveCont) if(c > 0) {
            targetCount[t++] = c;
        }

        // Secondly, let's remove dominated stickers. Because dominance is a transitive relation,
        // we only need to check if a sticker is not dominated by any other sticker once - the ones
        // that aren't dominated are included in our collection.
        int anchor = 0;
        for (int i = 0; i < stickers.length; i++) {
            for (int j = anchor; j < stickers.length; j++) if (j != i) {
                boolean dominated = true;
                for (int k = 0; k < t; k++) {
                    if (stickersCount[i][k] > stickersCount[j][k]) {
                        dominated = false;
                        break;
                    }
                }

                if (dominated) {
                    int[] tmp = stickersCount[i];
                    stickersCount[i] = stickersCount[anchor];
                    stickersCount[anchor++] = tmp;
                    break;
                }
            }
        }

        // We are now ready to begin our exhaustive search. A call to search(ans) denotes that
        // we want to decide the minimum number of stickers we can use in A to satisfy the target
        // count t_count. ans will store the currently formed answer, and best will store the
        // current best answer.
        best = target.length() + 1;
        search(0, anchor);
        return best <= target.length() ? best : -1;
    }

    private void search(int ans, int row) {
        // if our current answer can't beat our current best, we should stop searching. Also, if
        // there are no stickers left and our target is satisfied, we should update our answer.
        if (ans >= best) return;

        if (row == stickersCount.length) {
            for (int c : targetCount) if (c > 0) return;
            best = ans;
            return;
        }

        // Otherwise, we want to know the maximum number of these stickers we can use.
        int used = 0;
        for (int i = 0; i < stickersCount[row].length; i++) {
            if (targetCount[i] > 0 && stickersCount[row][i] > 0) {
                used = Math.max(used, (targetCount[i] - 1) / stickersCount[row][i] + 1);
            }
        }
        
        // After, for the sticker we are currently considering, we try to use used of them, then
        // used - 1, used - 2, ..., 1, 0. The reason we do it in this order is so that we can
        // arrive at a value for best more quickly, which will stop other branches of our exhaustive
        // search from continuing.
        for (int i = 0; i < stickersCount[row].length; i++) {
            targetCount[i] -= used * stickersCount[row][i];
        }

        search(ans + used, row + 1);

        while (used > 0) {
            for (int i = 0; i < stickersCount[row].length; i++) {
                targetCount[i] += stickersCount[row][i];
            }
            used--;
            search(ans + used, row + 1);
        }
    }

    public int minStickers1(String[] stickers, String target) {
        /*
         * Approach 2: Dynamic Programming
         * 
         * Suppose we need dp[state] stickers to satisfy all target[i]'s for which
         * the ith bit of state is set. We would like to know dp[(1 << len(target)) - 1].
         * 
         */
        int n = target.length();
        int[] dp = new int[1 << n];
        for (int i = 1; i < 1 << n; i++) dp[i] = -1;

        for (int state = 0; state < 1 << n; state++) {
            if (dp[state] == -1) continue;
            // For each state, let's work with it as now and look at what happens to it after
            // applying a sticker. 
            for (String sticker : stickers) {
                int now = state;

                // For each letter in the sticker that can satisfy an unset bit of state, we set
                // the bit (now |= 1 << i). In the end, we know now is the result of applying that
                // sticker to state, and we update our dp appropriately.
                for (char letter : sticker.toCharArray()) {
                    for (int i = 0; i < n; i++) {
                        if (((now >> i) & 1) == 1) continue;
                        if (target.charAt(i) == letter) {
                            now |= 1 << i;
                            break;
                        }
                    }
                }

                if (dp[now] == -1 || dp[now] > dp[state] + 1) {
                    dp[now] = dp[state] + 1;
                }
            }
        }

        return dp[(1 << n) - 1];
    }

    public int minStickers2(String[] stickers, String target) {
        int m = target.length();
        int[] memo = new int[1 << m];
        Arrays.fill(memo, -1);
        memo[0] = 0;
        int res = dp(stickers, target, memo, (1 << m) - 1);
        return res <= m ? res : -1;
    }

    public int dp(String[] stickers, String target, int[] memo, int mask) {
        int m = target.length();
        if (memo[mask] < 0) {
            int res = m + 1;
            for (String sticker : stickers) {
                int left = mask;
                int[] cnt = new int[26];
                for (int i = 0; i < sticker.length(); i++) {
                    cnt[sticker.charAt(i) - 'a']++;
                }
                for (int i = 0; i < target.length(); i++) {
                    char c = target.charAt(i);
                    if (((mask >> i) & 1) == 1 && cnt[c - 'a'] > 0) {
                        cnt[c - 'a']--;
                        left ^= 1 << i;
                    }
                }
                if (left < mask) {
                    res = Math.min(res, dp(stickers, target, memo, left) + 1);
                }
            }
            memo[mask] = res;
        }
        return memo[mask];
    }
}
